PriorityQueue/Heap Update

Question

Does Java have an easy way to reevaluate a heap once the priority of an object in a PriorityQueue has changed? I can't find any sign of it in Javadoc, but there has to be a way to do it somehow, right? I'm currently removing the object then re-adding it but that's obviously slower than running update on the heap.

Gilda

I'm curious what kind of answers result; I've run into this situation before & there didn't seem to be an easy answer. I doubt you can do better than O(log n). The remove(Object) method is the bottleneck from your current approach, it's linear in time. – Blackout

I usually just add the new item, without removing which is slow. To make the code correct, I keep a separate array or map with the elements that should have been removed, so when they show up, I can ignore them. – Psychoneurotic

possible duplicate of Updating Java PriorityQueue when its elements change priority – Nitrile

Answer 1

You might need to implement such a heap yourself. You need to have some handle to the position of the item in the heap, and some methods to push the item up or down when its priority has changed.

Some years ago I wrote such a heap as part of a school work. Pushing an item up or down is an O(log N) operation. I release the following code as public domain, so you may use it in any way you please. (You might want to improve this class so that instead of the abstract isGreaterOrEqual method the sort order would rely on Java's Comparator and Comparable interfaces, and also would make the class use generics.)

import java.util.*;

public abstract class Heap {

    private List heap;

    public Heap() {
        heap = new ArrayList();
    }

    public void push(Object obj) {
        heap.add(obj);
        pushUp(heap.size()-1);
    }

    public Object pop() {
        if (heap.size() > 0) {
            swap(0, heap.size()-1);
            Object result = heap.remove(heap.size()-1);
            pushDown(0);
            return result;
        } else {
            return null;
        }
    }

    public Object getFirst() {
        return heap.get(0);
    }

    public Object get(int index) {
        return heap.get(index);
    }

    public int size() {
        return heap.size();
    }

    protected abstract boolean isGreaterOrEqual(int first, int last);

    protected int parent(int i) {
        return (i - 1) / 2;
    }

    protected int left(int i) {
        return 2 * i + 1;
    }

    protected int right(int i) {
        return 2 * i + 2;
    }

    protected void swap(int i, int j) {
        Object tmp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, tmp);
    }

    public void pushDown(int i) {
        int left = left(i);
        int right = right(i);
        int largest = i;

        if (left < heap.size() && !isGreaterOrEqual(largest, left)) {
            largest = left;
        }
        if (right < heap.size() && !isGreaterOrEqual(largest, right)) {
            largest = right;
        }

        if (largest != i) {
            swap(largest, i);
            pushDown(largest);
        }
    }

    public void pushUp(int i) {
        while (i > 0 && !isGreaterOrEqual(parent(i), i)) {
            swap(parent(i), i);
            i = parent(i);
        }
    }

    public String toString() {
        StringBuffer s = new StringBuffer("Heap:\n");
        int rowStart = 0;
        int rowSize = 1;
        for (int i = 0; i < heap.size(); i++) {
            if (i == rowStart+rowSize) {
                s.append('\n');
                rowStart = i;
                rowSize *= 2;
            }
            s.append(get(i));
            s.append(" ");
        }
        return s.toString();
    }

    public static void main(String[] args){
        Heap h = new Heap() {
            protected boolean isGreaterOrEqual(int first, int last) {
                return ((Integer)get(first)).intValue() >= ((Integer)get(last)).intValue();
            }
        };

        for (int i = 0; i < 100; i++) {
            h.push(new Integer((int)(100 * Math.random())));
        }

        System.out.println(h+"\n");

        while (h.size() > 0) {
            System.out.println(h.pop());
        }
    }
}

Dithionite

This is exactly what I'm looking for. I simply doesn't want to implement this for the time being, but need to use it. I may release the improved version (as you've mentioned, I want to use generics and Comparator) sometime soon – Carlottacarlovingian

PushDown and PushUp are not enough, such things need a full heapify function which involves more steps. You can absolutely violate the heap property with the above code. – Cowen

Answer 2

PriorityQueue has the heapify method which re-sorts the entire heap, the fixUp method, which promotes an element of higher priority up the heap, and the fixDown method, which pushes an element of lower priority down the heap. Unfortunately, all of these methods are private, so you can't use them.

I'd consider using the Observer pattern so that a contained element can tell the Queue that its priority has changed, and the Queue can then do something like fixUp or fixDown depending on if the priority increased or decreased respectively.

Lola

Are you saying Java.util.priorotyqueue has those methods? I don't see them in the javadoc – Decadent

@Sridhar-Sarnobat Like Adam said, they're private so they won't show up in the java doc. – Polyandrist

Why Java do not make that heapify methods public then? It would be more customize-able and user friendly? What are the cons of making it public? – Wage

heapify() is called when you execute removeIf(..). Therefore if you don't mind the O(n) effort by this method you can call removeIf(x -> false) which will implicitly call heapify() at the end after removing nothing. – Megasporangium

Answer 3

The standard interfaces don't provide an update capability. You have use a custom type that implements this.

And you're right; although the big-O complexity of algorithms that use a heap doesn't change when you remove and replace the top of the heap, their actual run time can nearly double. I'd like to see better built-in support for a peek() and update() style of heap usage.

Althing

+1 for update capabilities. And I also would like to have the standard java Queue or Dequeue have a better implementation for high data volumes. It's really easy to home-cook an implementation that is 30% faster. – Shack

12 years later, and still not any better built-in support. – Austerlitz

Answer 4

That's right. PriorityQueue of Java does not offer a method to update priority and it seems that deletion is taking linear time since it does not store objects as keys, as Map does. It in fact accepts same object multiple times.

I also wanted to make PQ offering update operation. Here is the sample code using generics. Any class that is Comparable can be used with it.

class PriorityQueue<E extends Comparable<E>> {
    List<E> heap = new ArrayList<E>();
    Map<E, Integer> map = new HashMap<E, Integer>();

    void insert(E e) {
        heap.add(e);
        map.put(e, heap.size() - 1);
        bubbleUp(heap.size() - 1);
    }

    E deleteMax() {
        if(heap.size() == 0)
            return null;
        E result = heap.remove(0);
        map.remove(result);
        heapify(0);
        return result;
    }

    E getMin() {
        if(heap.size() == 0)
            return null;
        return heap.get(0);
    }

    void update(E oldObject, E newObject) {
        int index = map.get(oldObject);
        heap.set(index, newObject);
        bubbleUp(index);
    }

    private void bubbleUp(int cur) {
        while(cur > 0 && heap.get(parent(cur)).compareTo(heap.get(cur)) < 0) {
            swap(cur, parent(cur));
            cur = parent(cur);
        }
    }

    private void swap(int i, int j) {
        map.put(heap.get(i), map.get(heap.get(j)));
        map.put(heap.get(j), map.get(heap.get(i)));
        E temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }

    private void heapify(int index) {
        if(left(index) >= heap.size())
            return;
        int bigIndex = index;
        if(heap.get(bigIndex).compareTo(heap.get(left(index))) < 0)
            bigIndex = left(index);
        if(right(index) < heap.size() && heap.get(bigIndex).compareTo(heap.get(right(index))) < 0)
            bigIndex = right(index);
        if(bigIndex != index) {
            swap(bigIndex, index);
            heapify(bigIndex);
        }
    }

    private int parent(int i) {
        return (i - 1) / 2;
    }

    private int left(int i) {
        return 2*i + 1;
    }

    private int right(int i) {
        return 2*i + 2;
    }
}

Here while updating, I am only increasing the priority (for my implementation) and it is using MaxHeap, so I am doing bubbleUp. One may need to heapify based on requirement.

Careless

This code has two problems: 1. when an item is removed from heap in deleteMax, the values of map are now wrong; 2. swap incorrectly swaps the values of map - you need to use a temporary variable. As such it simply doesn't work in its current form. – Mercurio

Answer 5

Depending on the implementation of the data structure, there may not be a faster way. Most PQ/heap algorithms do not provide an update function. The Java implementation may not be any different. Notice that though a remove/insert makes the code slower, it is unlikely to result in code with a different runtime complexity.

Edit: have a look at this thread: A priority queue which allows efficient priority update?

Earleenearlene

Answer 6

Unfortunately, JDK's Priority Queue doesn't provide updates. Robert Sedgewick and Kevin Wayne are well known for their algorithms courses in Princeton, and they also wrote Algorithms.

Inside this excellent book, they provide their own implementations for data structures, including updateable priority queues, such as IndexMinPQ.java

Licensed under GPLv3.

Ioves

Answer 7

You need to implement it yourself. But you don't have to get fancy. The actual massive timesuck of removing the heap item in Java's implementation of remove(Object) is actually indexOf() since it has to iterate the entire list to find the index of the particular object. If you implement your own datastructure you can tell each object the position in the array and even if your implementation isn't anything fancy it'll outperform Java's since each object would know where its located in the array.

Storing that information you can do just the classic remove and add the new item and you'll beat Java by a lot.

The update routine just calls heapify on the particular index. It saves a heapify call, and some constant operations. The bulk of the optimization here is that Java's actual PriorityQueue can't store the index. So remove(Object) is actually a pretty expensive operation within that datastructure. As you're going to have to locate that Object in the list. This particular class reduces the time taken by PriorityQueue to nearly nothing. Though it requires that you implement Heap.Indexed on the items you put in the heap.

import java.util.Arrays;

public class Heap<T extends Heap.Indexed<T>> {

    private Indexed[] heap;
    private int length = 0;

    public Heap() {
        heap = new Indexed[12];
    }

    private void ensureCapacity() {
        if (length > heap.length) {
            heap = Arrays.copyOf(heap, length * 2);
        }
    }

    public void add(T obj) {
        int index = length++;
        ensureCapacity();
        obj.setIndex(index);
        heap[index] = obj;
        heapify(index);
    }

    public T removeAt(int index) {
        T result = get(index);
        length -= 1;
        if ((length > 0) && (index != length)) {
            swap(index, length);
            heapify(index);
        }
        result.setIndex(-1);
        heap[length] = null;
        return result;
    }

    public T remove(T obj) {
        int index = obj.getIndex();
        if (index == -1) {
            return null;
        }
        return removeAt(index);
    }

    public void update(T obj) {
        int index = obj.getIndex();
        obj.setIndex(-1);
        if (index == -1) {
            return;
        }
        heapify(index);
    }

    public T poll() {
        if (length == 0) {
            return null;
        }
        return removeAt(0);
    }

    public T peek() {
        return get(0);
    }

    public T get(int index) {
        return (T) heap[index];
    }

    public int size() {
        return length;
    }

    protected boolean compare(int first, int last) {
        return get(first).compareTo(get(last)) > -1;
    }

    protected void swap(int i, int j) {
        T tmp = (T) heap[i];
        heap[i] = (T) heap[j];
        heap[j] = tmp;
        heap[i].setIndex(i);
        heap[j].setIndex(j);
    }

    public void heapify(int index) {
        int parent = (index - 1) / 2;
        if (index > 0 && !compare(parent, index)) {
            swap(parent, index);
            heapify(parent);
            return;
        }
        int left = (index << 1) + 1;
        int right = left + 1;
        int largest = index;

        if (left < length && !compare(largest, left)) {
            largest = left;
        }
        if (right < length && !compare(largest, right)) {
            largest = right;
        }

        if (largest != index) {
            swap(largest, index);
            heapify(largest);
        }
    }

    public boolean isEmpty() {
        return length == 0;
    }

    public void clear() {
        this.length = 0;
        Arrays.fill(heap, null);
    }

    public interface Indexed<I extends Heap.Indexed> extends Comparable<I> {

        int getIndex();

        void setIndex(int index);
    }

}

Cowen